package Queue;

/**
 * 采用数组模拟循环队列
 * 分析一下普通的队列的弊端：
 *  首先我们知道队列是先进先出的数据结构，每次将元素从一端进队，然后从一端出队，对于对于入队操作
 *  我们可以设置一个rear指针，每次指向当前啊进入的元素(rear+1)，但是出队操作，由于先进先出的特
 *  点，将头元素出队之后，我们需要将队列之后的元素整体前移动一位，时间复杂度为O(n)。为了优化出队
 *  操作的时间复杂度，我们额外设置一个指向队头前一位的指针front，每次进行出队操作即front+1，然后
 *  此时front就指向当前的队头位置，但是这样又会出现一个弊端，具体如下：
 *      [null    null    3    4    5]
 *               front            rear
 *  由于数组的边界问题，此时rear无法移动，否则抛出数组索引越界异常，但是队列此时并没有满，所以上述
 *  的缺点就在于对于空间利用率不高，所以我们采用循环队列来解决这个问题
 */
/**
 *
 * 分析如何使用一个循环队列：
 *    即让队列的头尾相连。这并不是物理意义上的相连，而是通过索引之间的关系来实现一个循环的效果。
 *    对于队列而言我们的主要操作如下：
 *      1. 出队
 *      2. 入队
 *      3. 判断是否为空
 *      4. 判断是否为满
 *    先分析出队操作，出队操作移动的是front指针，考虑如下的情况
 *          [1,  2,  3,   null,   null]
 *         rear                   front
 *    此时front如果直接前移动一位，索引越界，所以我们可以采用取余的方式 front = (front + 1) % maxsize
 *    这样front变为0，恰好指向当前头元素，这是边界情况
 *    对于中间情况上述同理可知
 *
 *    入队操作，入队操作移动的是rear指针，考虑情况与上述完全一致 rear = (rear + 1) % maxsize;
 *
 *    判断是否为空
 *      由于front指针指向头的前一个元素，rear恰好指向队尾元素。如果当前只有一个元素，将其取出之后整个队列就空了
 *      rear一定指向的是这个元素，因为由后进后出的特性，当前元素一定是最后进入队列中的，在根据rear的特点，所以，
 *      此时rear一定指向当前最后一个元素，而front为当前元素的前一个，此时我们发现如果当前出队之后front == rear
 *
 *    判断是否为满
 *      同上述的分析，此时的判断满的条件也是 front = rear
 *
 *    问题来了，如何区分上述两种情况呢?
 */
/**
 * 对于上述循环队列的判断空满的三种解决方式
 *  1. 直接设置一个额外的变量记录当前队列中的实际元素，如果添加一个元素，自增，如果出队一个元素，自减
 *  2. 浪费掉一个空间的，即如果当前的队列最大长度为maxsize，则实际我们用的最大空间只有maxsize-1
 *      具体 [1,2,3, null,  5]
 *                   f     r   此时就是一个满的状态
 *           [1,2,3,4, null]
 *            r          f
 *      上述对应两种满的状态：f < r 或者 r < f
 *      所以此时的判断满条件为 (front+1) % maxsize == rear
 *      判断空依然是 front == rear
 *   3. 采用链表的方式解决循环队列，此时就不需要考虑索引越界问题了
 */

import java.util.concurrent.locks.ReentrantLock;

/**
 * 设计1   采用的是第一种解决方式
 */
class MyCircularQueue1 {

    // 采用数组的结构模拟队列
    int[] CircleDeque; // 循环队列容器
    int maxsize; // 循环队列的最大长度
    int front; // 指向头的前一个位置
    int rear; // 指向队列的尾部元素
    int count; // 记录当前队列中的有效元素个数

    // 初始化相关成员属性的初始值
    public MyCircularQueue1(int k) {
        CircleDeque = new int[k];
        maxsize = k;
        front = -1;
        rear = -1;
        count = 0;
    }

    // 入队操作
    public boolean enQueue(int value) {
        // 判断当前队列是否为满
        if(isFull()) {
            return false;
        }
        CircleDeque[(rear+1) % maxsize] = value;
        count++;
        rear = (rear+1) % maxsize;
        return true;
    }

    // 出队操作
    public boolean deQueue() {
        // 判断当前队列是否为空
        if(isEmpty()) {
            return false;
        }
        front = (front+1) % maxsize; // 需要删除的元素的索引
        count--;
        return true;
    }

    // 获取队首元素
    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return CircleDeque[(front+1) % maxsize];
    }

    // 获取队尾元素
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        return CircleDeque[rear];
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == maxsize;
    }
}

/**
 * 设计2    采用的是第二种解决方式
 */
class MyCircularQueue2 {

    // 采用数组的结构模拟队列
    int[] CircleDeque; // 循环队列容器
    int maxsize; // 循环队列的最大长度
    int front; // 指向头的前一个位置
    int rear; // 指向队列的尾部元素

    // 初始化相关成员属性的初始值
    public MyCircularQueue2(int k) {
        CircleDeque = new int[k];
        maxsize = k;
        front = -1;
        rear = -1;
    }

    // 入队操作
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        rear = (rear + 1) % maxsize;
        CircleDeque[rear] = value;
        return true;
    }

    // 出队操作
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % maxsize;
        return true;
    }

    // 获取队首元素
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return CircleDeque[(rear + 1) % maxsize];
    }

    // 获取队尾元素
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return CircleDeque[(front + 1) % maxsize];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (front + 1) % maxsize == rear;
    }

}

/**
 * 设计3  上述两种设计都是线程不安全的，下面我们设计一个线程安全的队列
 * (将设计1修改为线程安全的)  使用jkd提供的锁对象 java.util.concurrent.locks.ReentrantLock
 * 也可以直接使用synchronized关键字，或者同步代码块来实现，但是这两种方式都是重量级锁，资源消耗比较大
 */
class MyCirclarQueue3 {
    // 采用数组的结构模拟队列
    int[] CircleDeque; // 循环队列容器
    int maxsize; // 循环队列的最大长度
    int front; // 指向头的前一个位置
    int rear; // 指向队列的尾部元素
    int count; // 记录当前队列中的有效元素个数
    ReentrantLock reentrantLock; // 所对象，实现线程安全的


    // 初始化相关成员属性的初始值
    public MyCirclarQueue3(int k) {
        CircleDeque = new int[k];
        maxsize = k;
        front = -1;
        rear = -1;
        count = 0;
        reentrantLock = new ReentrantLock();
    }

    // 入队操作
    public boolean enQueue(int value) {
        // 判断当前队列是否为满
        if(isFull()) {
            return false;
        }
        reentrantLock.lock(); // 上锁，每次只允许一个线程对其进行修改
        try {
            CircleDeque[(rear+1) % maxsize] = value;
            count++;
            rear = (rear+1) % maxsize;
            return true;
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            reentrantLock.unlock(); // 开锁
        }
        return false;
    }

    // 出队操作
    public boolean deQueue() {
        // 判断当前队列是否为空
        if(isEmpty()) {
            return false;
        }
        reentrantLock.lock(); // 上锁
        try {
            front = (front+1) % maxsize; // 需要删除的元素的索引
            count--;
            return true;
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            reentrantLock.unlock();
        }
        return false;
    }

    // 获取队首元素
    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return CircleDeque[(front+1) % maxsize];
    }

    // 获取队尾元素
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        return CircleDeque[rear];
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == maxsize;
    }
}


/**
 * 设计4 采用循环链表实现
 */
class MyCircularQueue {
    /**
     * 采用内部类的方式定义节点类
     */
    class Node {
        int value;
        Node nextNode;

        public Node(int value) {
            this.value = value;
            this.nextNode = null;
        }
    }

    Node head, tail;
    int count;
    int capacity;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        this.capacity = k;
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (this.count == this.capacity)
            return false;

        Node newNode = new Node(value);
        if (this.count == 0) {
            head = tail = newNode;
        } else {
            tail.nextNode = newNode;
            tail = newNode;
        }
        this.count += 1;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (this.count == 0)
            return false;
        this.head = this.head.nextNode;
        this.count -= 1;
        return true;
    }

    /** Get the front item from the queue. */
    public int Front() {
        if (this.count == 0)
            return -1;
        else
            return this.head.value;
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if (this.count == 0)
            return -1;
        else
            return this.tail.value;
    }

    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return (this.count == 0);
    }

    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return (this.count == this.capacity);
    }
}



public class CircleDequeByArray {
    public static void main(String[] args) {

    }
}